package lanqiao14;
// OK
import java.util.Arrays;


public class A {
	private static final int N = 1000000 ;
	private static int count = 0;
	private static boolean isPrime[] = new boolean[N + 1];// 各个数对应的boolean数组是否为质数
	
	public static void main(String[] args) {
		/*
		 *                                 X 质数
		 *  对于一个含有M个数位的正整数N,任意选中其中K个不同的数位(0≤K<M),将这些选中的数位删除之后，
		 *  余下的数位按照原来的顺序组成了一个新的数字P。如果至少存在一个P是质数，我们就称N是一个X质数。
		 *  例如，对于整数7869，我们可以删去7和6，得到一个新的数字89，由于89是一个质数，因此7869是一个X质数。
		 *  又如，对于整数77，可以删去一个7后变为质数7，因此77也是一个X质数。
		 *  请问1（含）至1000000（含）中一共有多少个不同的X质数。
		 */
		st_();
		for (int i = 1; i <= N; i++) {
			if (isXPrime(Integer.toString(i))) {
				count++;
			}
		}
		System.out.println(count);
		System.out.println(isPrime[1000000]);
		System.out.println(isXPrime("1000000"));
	}
	
	// 遍历1000000，使 isPrime[] 数组中对应的位置质数为 true ，非质数为 false
	private static void st_(){
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;
	    for(int i = 2;i * i <= N;i++){
	        if (isPrime[i]) {
				for (int j = i * i; j <= N; j += i) {
					isPrime[j] = false;
				}
			}
	    }
	}
	
	// 判断 num 是不是 X质数
	private static boolean isXPrime(String num) {
		if (isPrime[Integer.parseInt(num)]) {
			return true;
		}
		
		for (int i = 0; i < num.length(); i++) {
			String newNum = num.substring(0, i) + num.substring(i + 1);
			if (!newNum.isEmpty() && isXPrime(newNum)) {
				return true;
			}
		}
		return false;
	}
}







































